package com.scott.ch160;

/**
 * @author 黄后林
 * @version 1.0
 * @note
 * @date 2022-03-14 15:16:20
 */
public class Heap<T extends Comparable<T>> {

    //存储堆中的元素
    private T[] items;

    //堆中元素的个数
    private int counter;

    public Heap(int capacity) {

        // 初始化数组、并指定元素的个数
        this.items= (T[]) new Comparable[capacity+1];

        //初始化元素个数为0
        this.counter = 0;
    }

    //下标=i的元素小于下标=j的元素则返回true、否则返回false
    private boolean less(int i,int j){

        if(this.items[i].compareTo(this.items[j])<0){
            return true;
        }
        return false;
    }

    //交换位置
    private void exch(int i,int j){
        T tmp=items[i];
        items[i]=items[j];
        items[j]=tmp;

    }

    //往堆中插入一个元素
    public void insert(T t){
        // 元素增加1个
        this.counter=this.counter+1;

        //为了更方便地计算下标、把下标为0的位置抛弃掉、不放元素。从下标1开始。
        //把0索引废弃掉
        this.items[this.counter]=t;

        //先在堆的最后面插入、如果子节点比父节点大 需要上浮
        swim(this.counter);

    }

    //使用上浮算法、使下标=k的元素能在堆中找到一个正确的位置
    //上浮：下层元素变成上层元素=升官
    //上浮之后堆依然有序
    private void swim(int k ){

        //1 通过循环、不断地比较当前节点的值和父节点的值 [ 如果父节点比当前节点小 则交换位置 ]

        while( k>=2 ){
            // 当k=2的时候 说明已经到了根节点的的下一层 此时只需要把子节点和根节点比较即可
            // 如果k=1 说明此时当前元素已经是根节点 在堆中 根节点是最大的元素
            if(less(k/2,k)){
                // 如果父节点比当前节点小 则交换位置

                //交换位置
                exch(k/2,k);
            }
            // 修改步长
            k=k/2;
        }


    }

    //使用下沉算法、使下标=k的元素能在堆中找到一个正确的位置
    //下沉：上层元素变成下层元素=降职
    //下沉之后堆依然有序
    private void sink(int k ){

        //通过循环 对比根节点和2个子节点中的较大者 如果根节点比较大者小 交换位置
        // 跟节点为k 它的2个子节点分别为2k和2k+1

        while(2*k <= this.counter){
            //这样才能保证最少有1个左节点


            //1 获取子节点中的较大者 所在的下标
            int max;
            if(2*k+1< this.counter){
                //说明有右子节点
                if(less(2*k,2*k+1)){
                    max=2*k+1;
                }else{
                    max=2*k;
                }
            }else{
                //说明没有右子节点  只有左子节点
                max = 2*k;
            }
            if(!less(k,max)){
                // 如果根节点比较大者大 结束循环
                break;
            }

            // 如果没有break  说明根节点比较大者小 交换位置
            exch(k,max);

            // 修改k的值 修改步长 为下次循环做准备
            k=max;

        }


    }

    //删除堆中最大的元素、并返回这个元素
    public T deleteMax(){

        T max = this.items[1];

        //1、交换下标=1的元素和下标最大的元素 [ 让完全二叉树最右侧的节点变成临时根节点 ]
        exch(1,this.counter);

        //2、删除最大索引出的元素
        this.items[this.counter]=null;

        //3、堆中的元素个数-1
        this.counter--;
        //4、通过节点下沉让堆重新有序
        sink(1);

        return max;
    }
}
